2026a 第05回:オペレーティングシステム

アナウンス

直前のご連絡で申し訳ない、本日オンライン開催です

小テストは次週持ち越し

出席は Zoomの出席アカウントをベースに確認します

keio.jpのアカウントでzoomへの参加をお願いします！ (個人メアド x iPhoneという名前では出席特定できません）

前回授業の振り返り

レポート提出の分布

ダイクストラ法 ... 8名

幅優先探索 ... 8名

クイックソート ... 8名

ダイクストラ法について

用途

最短経路探索

前提となるデータ構造

グラフデータ構造

各地点(ノード)と経路(エッジ)、およびエッジの重み(移動コスト)を持つ

考え方

0. 各ノードに「暫定距離」の情報を持たせ、始点は0、それ以外は無限大、としておく

1. 始点に隣接するノードを調査、それぞれのノードに「暫定距離」を入れる

隣接するノードとの距離が全て埋まったらそのノードは「確定済み(out)」

2. 未確定ノードのうち最も暫定距離が低いものに対して、1の処理を繰り返す

3. 目的ノードが確定するか、未確定ノードが無くなるまで繰り返す

https://upload.wikimedia.org/wikipedia/commons/5/57/Dijkstra_Animation.gif

講義

TSSとバッチシステムの違い

いずれも「キュー」の概念だが、処理する単位が異なる

バッチシステムは「ジョブ」単位で一括処理

TSS は、複数ユーザーのプログラムやコマンドを短い時間に区切って切り替えながら順次処理

実習5-2,5-3 バッチシステムとTSS

「待ち時間」と「ターンアラウンドタイム」

待ち時間(Waiting Time) ... CPUをもらえずに待っている時間の合計

ターンアラウンドタイム (TurnAround Time) … 待ち時間+処理が終わるまでの総時間

3つの条件でWTとTATを比較してみよう

table: 比較表

ケース avg. Waiting Time avg. TurnAround Time

a. バッチシステム x Aから着手 (0h+5h)/2 = 2.5h (5h+(5h+1h))/2 = 5.5h

b. バッチシステム x Bから着手 (1h+0h)/2 = 0.5h ((1h+5h)+1h)/2 = 3.5h

c. TSS x 同時に着手 (0h+0h)/2 = 0h (1h*2+(5-1h*2/2)+1h*2)/2 = 4h

タイピングテスト